class Solution {
    int[][] memo;
    public int getMoneyAmount(int n) {
        memo = new int[n + 1][n + 1];
        return dfs(1, n);
    }
    public int dfs(int s, int e) {
        int ret = Integer.MAX_VALUE;
        if(s >= e) {
            return 0;
        }
        if(memo[s][e] != 0) return memo[s][e];
        for(int i = s; i <= e; i++) {
            int left = dfs(s, i - 1);
            int right = dfs(i + 1, e);
            ret = Math.min(Math.max(left, right) + i, ret);
        }
        memo[s][e] = ret;
        return ret;
    }
}